Advances in data flow programs for digital signal processing has provided significant progress in circuit optimization using data flow graphs, especially for parallel computers. A data flow graph representation is a popular hardware and software methodology where algorithms are described as directed graphs with nodes representing computations (or functions or subtasks) and edges representing data paths (communications between nodes). A data flow algorithm is mainly concerned with the flow of data and not with the actual computation process, and is a natural paradigm for describing digital signal processing applications for concurrent implementation on parallel hardware. For concurrent implementations, a task is broken into subtasks that are then scheduled onto parallel processors.
For example, FIG. 1A illustrates a circuit block diagram describing the computation y[n]=ay[n−1]+x[n]. This is a feedback function where the computational output y[n] depends on the value of its previous output y[n−1]. The block diagram shows a delay block D, which can be a delay register, to store the previous value of the output y. A multiplication block X is provided to multiply the delay output y[n−1] and a constant a. An addition block + is provided to add the input x[n] with the multiplied delay output ay[n−1]. A key feature of a circuit block diagram is that the functionality of the circuit can be understood and derived from the circuit block diagram. For example, the computation y[n]=ay[n−1]+x[n] can be calculated from the circuit block diagram of FIG. 1A at a circuit operation level.
FIG. 1B illustrates a data flow graph of this block diagram with node A representing the addition block and node B representing the multiplication block. The edge from B to A (B→A) represents the data path from the multiplication block to the addition block, and the edge from A to B (A→B) represents the data path from the addition block to the multiplication block. The delay D is inserted to the data path from A to B to show that the edge from A to B (A→B) contains one delay (e.g., 1 clock cycle delay). The input branch x[n] and the output branch y[n] are shown in dotted lines, mainly for an illustration of the correlation with the block diagram of FIG. 1A. In practice, the input and output branches are typically not shown in a data flow graph (e.g., FIG. 1C). Alternatively, the delay D can be shown in the vicinity of the edge (FIG. 1C).
Other information can be included in the data flow graph, for example, information related to synchronous data flow graph to show that execution of nodes A and B consumes one data sample and produces output. This is illustrated by a number 1 from the edge coming to node A/B and a number 1 from the edge coming out of node A/B. Each node can have an execution time associated with it, for example, the amount of time required to execute node A (addition computation) is 2 time units (e.g., 2 clock cycles), and the amount of time required to execute node B (multiplication computation) is 4 time units. This is illustrated by a number in parentheses (2) and (4) in the vicinity of nodes A and node B, respectively.
Typically, operations of a data flow graph at a data flow level are operations related only to the data flow without regard to functional or computational operations. For example, the critical path of a data flow graph is defined to be the path with the longest computation time among all paths that contain zero delay. Thus the critical path in the data flow graph shown in FIG. 1B is the path B→A, which requires 6 time units. Optimizing the critical path is an example of optimizing a data flow graph at a data flow level.
The illustrated data flow graph describes a single rate system where all nodes consume one data sample and produce one output relative to a clock cycle. In multirate systems, the number of data samples consumed and produced can be different than 1, such as in a system where the nodes operate at different frequencies or a decimator or an interpolator. For example, a ↓2 decimator rejects every other data sample, thus producing one data output for every 2 data samples consumed. A ↑2 interpolator introduces an addition data output for every data sample, thus producing 2 data outputs for every 1 data sample consumed.
In addition to being natural to digital signal processing, a data flow graph representation has another advantage of generating the same results for any implementations of the data flow description, as long as the integrity of the flow of data is preserved. Thus, data flow graph representations can be an indispensable tool in scheduling and mapping circuit design representation onto hardware.
The current data flow graph representations employ nodes and edges, together with using linear programming to optimize the flow of data to achieve a desired clock.